package leetcode.weekly.week310;

//Solution4Test
public class Solution4 {

	int FULL = (int) 1e5 + 5;

	public int lengthOfLIS(int[] nums, int k) {
		Node tree = new Node(FULL);
		int ans = 1;
		for (int i = 0; i < nums.length; i++) {
			int num = nums[i];
			int R = num - 1 + 1, L = num - k + 1;
			int max = (int) tree.query(L, R, 1, FULL, 1);
			ans = Math.max(ans, max + 1);
			tree.update(num + 1, num + 1, max + 1, 1, FULL, 1);
		}
		return ans;
	}

	class Node {
		int RANGE;
		int[] max;
		Integer[] update;

		public Node(int len) {
			int n = len + 1;
			RANGE = n << 2;
			max = new int[RANGE];
			update = new Integer[RANGE];
		}

		private int left(int root) {
			return root << 1;
		}

		private int right(int root) {
			return root << 1 | 1;
		}

		private int mid(int l, int r) {
			return (l + r) >> 1;
		}

		private void max(int root) {
			max[root] = Math.max(max[root << 1], max[root << 1 | 1]);
		}

		public void update(int L, int R, int A, int l, int r, int root) {
			if (L <= l && r <= R) {
				max[root] = Math.max(max[root], A);
				update[root] = Math.max(max[root], A);
			} else {
				int mid = this.mid(l, r);
				this.push(root, mid - l + 1, r - mid);
				if (L <= mid) {
					this.update(L, R, A, l, mid, this.left(root));
				}
				if (R > mid) {
					this.update(L, R, A, mid + 1, r, this.right(root));
				}
				this.max(root);
			}
		}

		private void push(int root, int ls, int rs) {
			int l = this.left(root), r = this.right(root);
			if (update[root] != null) {
				int a = update[root];
				this.pushUpdate(l, a, ls);
				this.pushUpdate(r, a, rs);
				update[root] = null;
			}
		}

		private void pushUpdate(int root, int A, int size) {
			update[root] = Math.max(max[root], A);
			max[root] = Math.max(max[root], A);
		}

		public long query(int L, int R, int l, int r, int root) {
			if (L <= l && r <= R) {
				return max[root];
			}
			int mid = this.mid(l, r);
			this.push(root, mid - l + 1, r - mid);
			long ans = 0;
			if (L <= mid) {
				ans = this.query(L, R, l, mid, this.left(root));
			}
			if (R > mid) {
				ans = Math.max(ans, this.query(L, R, mid + 1, r, this.right(root)));
			}
			return ans;
		}

	}

}
